package cn.topcode.unicorn.utils.tree;

import org.springframework.util.Assert;
import java.io.Serializable;
import java.util.*;

public class Tree implements Serializable {

    private Map<String, TreeNode> index = new HashMap<>();

    private List<TreeNode> root = new ArrayList<>();

    /**
     * 加载为树型结构
     * @param entitys
     */
    public static Tree load(List<? extends TreeEntity> entitys) {
        Tree tree = new Tree();

        Map<String, List<TreeNode>> map = new HashMap<>();
        for(TreeEntity entity : entitys) {
            if(entity.getId() == null) {
                continue;
            }
            if(!tree.index.containsKey(entity.getId().toString())) {

                TreeNode treeNode = new TreeNode();
                treeNode.setId(entity.getId());
                treeNode.setChildrens(new ArrayList<>());
                treeNode.setData(entity);

                tree.index.put(entity.getId().toString(), treeNode);

                if(entity.getParentId() == null) {
                    tree.root.add(treeNode);
                }else {
                    List<TreeNode> list = null;
                    if(map.containsKey(entity.getParentId().toString())) {
                        list = map.get(entity.getParentId().toString());
                    }
                    if(list == null) {
                        list = new ArrayList<>();
                        map.put(entity.getParentId().toString(), list);
                    }
                    list.add(treeNode);
                }
            }
        }

        loadTree(map, tree.root, null);

        return tree;
    }

    private static void loadTree(Map<String, List<TreeNode>> map, List<TreeNode> nodes, TreeNode parent) {
        for(TreeNode node : nodes) {
            node.setParentId(parent != null ? parent.getId() : null);
            List<TreeNode> childs = null;
            if(map.containsKey(node.getId().toString())) {
                childs = map.get(node.getId().toString());
            }
            if(childs != null) {
                node.getChildrens().addAll(childs);
                loadTree(map, childs, node);
            }
        }
    }

    /**
     * 通过父级id查找子节点
     * @param parentId
     * @return
     */
    public List<TreeNode> findByParentId(Long parentId) {
        if(parentId == null) {
            return root;
        }
        TreeNode node = index.get(parentId.toString());
        if(node == null) {
            return Collections.EMPTY_LIST;
        }
        return node.getChildrens();
    }

    /**
     * 通过id查找节点
     * @param id
     * @return
     */
    public TreeNode findById(Long id) {
        if(id == null) {
            return null;
        }
        return index.get(id.toString());
    }

    /**
     * 通过id查找节点数据
     * @param id
     * @param clazz
     * @param <T>
     * @return
     */
    public <T extends TreeEntity> T findById(Long id, Class<T> clazz) {
        TreeNode node = this.findById(id);
        if(node == null) {
            return null;
        }
        return (T) node.getData();
    }

    /**
     * 通过父id获取所有子节点的实体
     * @param parentId
     * @return
     */
    public List<TreeEntity> findTreeEntityByParentId(Long parentId) {
        List<TreeEntity> entitys = new ArrayList<>();
        List<TreeNode> nodes = this.findByParentId(parentId);
        for(TreeNode node : nodes) {
            entitys.add(node.getData());
            List<TreeEntity> subEntitys = findTreeEntityByParentId(node.getData().getId());
            entitys.addAll(subEntitys);
        }
        return entitys;
    }

    /**
     * 通过父id获取所有子节点的实体并转换为实体真实的数据类型
     * @param parentId
     * @param clazz
     * @param <T>
     * @return
     */
    public <T extends TreeEntity> List<T> findTreeEntityByParentId(Long parentId, Class<T> clazz) {
        List<TreeEntity> entitys = this.findTreeEntityByParentId(parentId);
        List<T> list = new ArrayList<>();
        for(TreeEntity entity : entitys) {
            list.add((T) entity);
        }
        return list;
    }

    /**
     * 通过id获取节点及所有子节点的实体
     * @param id
     * @return
     */
    public List<TreeEntity> findTreeEntityById(Long id) {
        List<TreeEntity> entitys = new ArrayList<>();

        TreeNode curNode = this.findById(id);
        if(curNode == null) {
            return Collections.EMPTY_LIST;
        }
        entitys.add(curNode.getData());

        List<TreeNode> nodes = this.findByParentId(curNode.getData().getId());
        for(TreeNode node : nodes) {
            entitys.add(node.getData());
            List<TreeEntity> subEntitys = findTreeEntityByParentId(node.getData().getId());
            entitys.addAll(subEntitys);
        }
        return entitys;
    }

    /**
     * 通过id获取节点及所有子节点的实体并转换数据类型
     * @param id
     * @param clazz
     * @param <T>
     * @return
     */
    public <T extends TreeEntity> List<T> findTreeEntityById(Long id, Class<T> clazz) {
        List<TreeEntity> entitys = this.findTreeEntityById(id);
        List<T> list = new ArrayList<>();
        for(TreeEntity entity : entitys) {
            list.add((T) entity);
        }
        return list;
    }

    /**
     * 判断subNodeId是否为parentId的子节点
     * @param parentId
     * @param subNodeId
     * @return
     */
    public boolean isSubTreeNode(Long parentId, Long subNodeId) {
        Assert.notNull(subNodeId, "子节点id不能为空");

        TreeNode parent = this.findById(parentId);
        Assert.notNull(parent, "父节点不存在");

        if(subNodeId.equals(parentId)) {
            return true;
        }
        for(TreeNode nodes : parent.getChildrens()) {
            if(subNodeId.equals(nodes.getData().getId())) {
                return true;
            }
            if(isSubTreeNode(nodes.getData().getId(), subNodeId)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 从指定节点开始向下搜索，匹配第一个符合条件的节点立即返回
     * @param startNodeId   为null表示从根节点开始
     * @param search
     * @return
     */
    public TreeNode searchDown(Long startNodeId, TreeNodeSearch search) {
        List<TreeNode> startNodes = findStartNodes(startNodeId);
        if(startNodes.isEmpty()) {
            return null;
        }
        List<TreeNode> nodes = search(startNodes, search, true, false);
        if(nodes.isEmpty()) {
            return null;
        }
        return nodes.get(0);
    }

    /**
     * 从指定节点开始向上搜索，匹配第一个符合条件的节点立即返回
     * @param startNodeId   为null表示从根节点开始
     * @param search
     * @return
     */
    public TreeNode searchUp(Long startNodeId, TreeNodeSearch search) {
        List<TreeNode> startNodes = findStartNodes(startNodeId);
        if(startNodes.isEmpty()) {
            return null;
        }
        List<TreeNode> nodes = search(startNodes, search, true, true);
        if(nodes.isEmpty()) {
            return null;
        }
        return nodes.get(0);
    }

    /**
     * 从指定节点开始向下搜索，匹配搜索所有符合条件的节点
     * @param startNodeId
     * @param search
     * @return
     */
    public List<TreeNode> searchListDown(Long startNodeId, TreeNodeSearch search) {
        List<TreeNode> startNodes = findStartNodes(startNodeId);
        if(startNodes.isEmpty()) {
            return startNodes;
        }
        return search(startNodes, search, false, false);
    }

    /**
     * 从指定节点开始向上搜索，匹配搜索所有符合条件的节点
     * @param startNodeId
     * @param search
     * @return
     */
    public List<TreeNode> searchListUp(Long startNodeId, TreeNodeSearch search) {
        List<TreeNode> startNodes = findStartNodes(startNodeId);
        if(startNodes.isEmpty()) {
            return startNodes;
        }
        return search(startNodes, search, false, true);
    }

    private List<TreeNode> findStartNodes(Long startNodeId) {
        List<TreeNode> startNodes = null;
        if(startNodeId == null) {
            startNodes = root;
        }else {
            TreeNode startNode = this.findById(startNodeId);
            if(startNode == null) {
                return new ArrayList<>();
            }
            startNodes = Arrays.asList(startNode);
        }
        return startNodes;
    }

    /**
     * 搜索树
     * @param startNodes    开始搜索的节点
     * @param search        搜索条件
     * @param one           匹配第一个立即返回
     * @param up            向上搜索；向下搜索
     * @return              符合条件的节点
     */
    private List<TreeNode> search(List<TreeNode> startNodes, TreeNodeSearch search, boolean one, boolean up) {
        List<TreeNode> ok = new ArrayList<>();
        for(TreeNode node : startNodes) {
            if(search.process(node)) {
                ok.add(node);
                if(one) {
                    return ok;
                }
            }
            if(up) {
                if(node.getParentId() != null) {
                    TreeNode parent = this.findById(node.getParentId());
                    if(parent != null) {
                        ok.addAll(search(Arrays.asList(parent), search, one, up));
                    }

                }
            }else {
                if(!node.getChildrens().isEmpty()) {
                    ok.addAll(search(node.getChildrens(), search, one, up));
                }
            }
        }
        return ok;
    }

    public void clear() {
        if(index.size() != 0) {
            index.clear();
        }
        if(!root.isEmpty()) {
            root.clear();
        }

    }
}
